package class5;

import common.TreeNode;
import common.TreeNodeUtils;
import sun.reflect.generics.tree.Tree;

/**
 * https://leetcode.cn/problems/path-sum/description/
 * 路径总和
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
 * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
 * 如果存在，返回 true ；否则，返回 false 。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 */
public class Code09_hasPathSum {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getTreeNode();
        boolean b = hasPathSum(treeNode, 19);
        System.out.println("b = " + b);
    }


    public static boolean isSum = false;

    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        isSum = false;
        process(root, 0, sum);
        return isSum;
    }

    private static void process(TreeNode x, int preSum, int sum) {
        /**
         * 叶子节点处理逻辑
         * 当 x.left 和 x.right 都为空时，节点为叶子节点
         * 判断有sum值是否成立。
         *
         * 当出现叶子节点的时刻，才可能出现sum
         */
        if (x.left == null && x.right == null) {
            if ((preSum + x.val) == sum) {
                isSum = true;
            }
            return;
        }
        /**
         *  非叶子节点
         */
        preSum += x.val;
        if (x.left != null) {
            process(x.left, preSum, sum);
        }
        if (x.right != null) {
            process(x.right, preSum, sum);
        }

    }
}
